/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/combination-sum-iv
   @Language: C++
   @Datetime: 19-06-04 13:45
   */

class Solution {
public:
	/**
	 * @param nums: an integer array and all positive numbers, no duplicates
	 * @param target: An integer
	 * @return: An integer
	 */
	int backPackVI(vector<int> &nums, int target) {
		// write your code here
		vector<int> dp(target+1,0);
		for(int i=0; i<=target; ++i){
			for(int j=0; j<nums.size(); ++j){
				if(i==nums[j]) dp[i]++;
				if(i>=nums[j]) dp[i]+=dp[i-nums[j]];
			}
		}
		return dp[target];
	}
};
